package com.daiyang.javabasics.test;

import java.util.*;

public class test {
    public static void main(String[] args) {
//        String s1="abc";
//        String s2="bad";
//        System.out.println(CheckPermutation(s1,s2));
        //groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"});
    //    System.out.println(longestConsecutive(new int[]{100, 4, 200, 1, 3, 2}));
        duplicateZeros(new int[]{0,1,1,7,6,0,0,2});

    }
    public static boolean CheckPermutation(String s1, String s2) {
        int len = s1.length();
        if (len != s2.length()) {
            return false;
        }
        char[] cs1 = s1.toCharArray();
        char[] cs2 = s2.toCharArray();
        int[] hash = new int[26];
        for (int i = 0; i < len; i++) {
            int x = cs1[i];
            hash[x - 97] += 1;
        }
        for (int i = 0; i < len; i++) {
            int x = cs2[i];
            hash[x - 97] -= 1;
            if (hash[x - 97] < 0) {
                return false;
            }
        }
        return true;

    }
    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list=new ArrayList<>();




        Map<String,List<String>> hash = new HashMap();
        for(int i=0;i<strs.length;i++) {
            if(hash.containsKey(sortS(strs[i]))) {
                List<String> l=hash.get(sortS(strs[i]));
                l.add(strs[i]);
                hash.put(sortS(strs[i]),l);
            } else {
                List<String> l=new ArrayList<String>();
                l.add(strs[i]);
                hash.put(sortS(strs[i]),l);
            }
        }
        return new ArrayList(hash.values());
    }
    private static  String sortS(String s) {
        char [] c =s.toCharArray();
        Arrays.sort(c);
        return new String(c);

    }

    public  static int longestConsecutive(int[] nums) {
        int len =nums.length;
        int [] hash =new int [len];
        for(int i=0;i<len;i++) {
            if(nums[i]<len&&nums[i]>=0) {
                hash[nums[i]]+=1;
            } else  if((0-nums[i])<len&&nums[i]<0){
                hash[0-nums[i]]+=1;
            }
        }
        int count=0;
        int temp=0;
        for(int i=0;i<len;i++) {
            if(hash[i]==0) {
                count =Math.max(count,temp);
                temp=0;
            } else {
                temp+=hash[i];
            }
        }
        count =Math.max(count,temp);
        return count;
    }
    public static void duplicateZeros(int[] arr) {
        int cur=0,dest=-1;
        for(;dest<arr.length-1;cur++) {
            if(arr[cur]==0) dest+=2;
            else dest++;
            if(dest==arr.length-1) {
                break;
            }

        }
        if(dest>arr.length-1) {
            dest--;
            arr[dest--]=0;
            cur--;
        }
        while(cur>=0&&dest>0) {
            if(arr[cur]==0) {
                arr[dest--]=0;
                arr[dest--]=0;
                cur--;
            } else {
                arr[dest--]=arr[cur--];
            }
        }
    }

}
